{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Range Product Queries of Powers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: productQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二的幂数组中查询范围内的乘积"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数&nbsp;<code>n</code>&nbsp;，你需要找到一个下标从&nbsp;<strong>0</strong>&nbsp;开始的数组&nbsp;<code>powers</code>&nbsp;，它包含 <strong>最少</strong>&nbsp;数目的 <code>2</code>&nbsp;的幂，且它们的和为&nbsp;<code>n</code>&nbsp;。<code>powers</code>&nbsp;数组是&nbsp;<strong>非递减</strong>&nbsp;顺序的。根据前面描述，构造&nbsp;<code>powers</code>&nbsp;数组的方法是唯一的。</p>\n",
    "\n",
    "<p>同时给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>queries</code>&nbsp;，其中&nbsp;<code>queries[i] = [left<sub>i</sub>, right<sub>i</sub>]</code>&nbsp;，其中&nbsp;<code>queries[i]</code>&nbsp;表示请你求出满足&nbsp;<code>left<sub>i</sub> &lt;= j &lt;= right<sub>i</sub></code>&nbsp;的所有&nbsp;<code>powers[j]</code>&nbsp;的乘积。</p>\n",
    "\n",
    "<p>请你返回一个数组<em>&nbsp;</em><code>answers</code>&nbsp;，长度与<em>&nbsp;</em><code>queries</code>&nbsp;的长度相同，其中<em>&nbsp;</em><code>answers[i]</code>是第<em>&nbsp;</em><code>i</code>&nbsp;个查询的答案。由于查询的结果可能非常大，请你将每个&nbsp;<code>answers[i]</code>&nbsp;都对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 15, queries = [[0,1],[2,2],[0,3]]\n",
    "<b>输出：</b>[2,4,64]\n",
    "<strong>解释：</strong>\n",
    "对于 n = 15 ，得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。\n",
    "第 1 个查询的答案：powers[0] * powers[1] = 1 * 2 = 2 。\n",
    "第 2 个查询的答案：powers[2] = 4 。\n",
    "第 3 个查询的答案：powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。\n",
    "每个答案对 10<sup>9</sup> + 7 得到的结果都相同，所以返回 [2,4,64] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 2, queries = [[0,0]]\n",
    "<b>输出：</b>[2]\n",
    "<strong>解释：</strong>\n",
    "对于 n = 2, powers = [2] 。\n",
    "唯一一个查询的答案是 powers[0] = 2 。答案对 10<sup>9</sup> + 7 取余后结果相同，所以返回 [2] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt; powers.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [range-product-queries-of-powers](https://leetcode.cn/problems/range-product-queries-of-powers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [range-product-queries-of-powers](https://leetcode.cn/problems/range-product-queries-of-powers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['15\\n[[0,1],[2,2],[0,3]]', '2\\n[[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            a.append(lb := n & -n)\n",
    "            n ^= lb\n",
    "        na = len(a)\n",
    "        res = [[0] * na for _ in range(na)]\n",
    "        for i, x in enumerate(a):\n",
    "            res[i][i] = x\n",
    "            for j in range(i + 1, na):\n",
    "                res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "        return [res[l][r] for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            a.append(lb := n & -n)\n",
    "            n -= lb\n",
    "        na = len(a)\n",
    "        res = [[0] * na for _ in range(na)]\n",
    "        for i, x in enumerate(a):\n",
    "            res[i][i] = x\n",
    "            for j in range(i + 1, na):\n",
    "                res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "        return [res[l][r] for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        na = len(a)\n",
    "        res = [[0] * na for _ in range(na)]\n",
    "        for i, x in enumerate(a):\n",
    "            res[i][i] = x\n",
    "            for j in range(i + 1, na):\n",
    "                res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "        return [res[l][r] for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            a.append(lb := n & -n)\n",
    "            n -= lb\n",
    "        na = len(a)\n",
    "        res = [[0] * na for _ in range(na)]\n",
    "        for i, x in enumerate(a):\n",
    "            res[i][i] = x\n",
    "            for j in range(i + 1, na):\n",
    "                res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "        return [res[l][r] for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        na = len(a)\n",
    "        res = [[0] * na for _ in range(na)]\n",
    "        for i, x in enumerate(a):\n",
    "            res[i][i] = x\n",
    "            for j in range(i + 1, na):\n",
    "                res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "        return [res[l][r] for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        len_a = len(a)\n",
    "        res = [[0] * len_a for _ in range(len_a)]\n",
    "        for i, x in enumerate(a):\n",
    "            res[i][i] = x\n",
    "            for j in range(i + 1, len_a):\n",
    "                res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "        return [res[l][r] for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        m = len(queries)\n",
    "        mod = 10**9+7\n",
    "        powers =[]\n",
    "        for i in range(32):\n",
    "            bit =n &1\n",
    "            n>>=1\n",
    "            if bit :\n",
    "                powers.append(1<<i)\n",
    "            \n",
    "        ans= []\n",
    "        for l,r in queries:\n",
    "            ret = 1 \n",
    "            for i in range(l,r+1):\n",
    "                ret *= powers[i] \n",
    "            ans.append(ret%mod)\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        # 最低位，并直接求前缀积\n",
    "        powers = [1]\n",
    "        while n:\n",
    "            n ^= (lb := n & -n)\n",
    "            powers.append(lb * powers[-1])\n",
    "            \n",
    "\n",
    "        # 前缀积\n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            ans.append(powers[right + 1] // powers[left] % MOD)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        power = []\n",
    "        tmp = 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                power.append(tmp)\n",
    "            n //= 2\n",
    "            tmp += 1\n",
    "        tmp = 10 ** 9 + 7\n",
    "        ret = []\n",
    "        pre = list(accumulate(power, initial=0))\n",
    "        for q in queries:\n",
    "            delta = pre[q[1]+1] - pre[q[0]]\n",
    "            ret.append(2 ** delta % tmp)\n",
    "        return list(map(int, ret))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        powers = []\n",
    "        while n:\n",
    "            x = n & -n # 取最低位的n\n",
    "            powers.append(x)\n",
    "            n ^= x\n",
    "        ans = [0] * len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            l, r = q\n",
    "            s = 1\n",
    "            for j in range(l, r + 1):\n",
    "                s = s * powers[j] % MOD\n",
    "            ans[i] = s\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        # 倍增法\n",
    "        mask = 1 << n.bit_length() - 1\n",
    "        powers = []\n",
    "        while mask > 0 and n > 0:\n",
    "            if n >= mask:\n",
    "                powers.append(mask)\n",
    "                n -= mask\n",
    "            mask >>= 1\n",
    "        # 前缀积\n",
    "        powers = [*accumulate(powers[::-1], mul, initial = 1)]\n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            ans.append(powers[right + 1] // powers[left] % MOD)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        # 倍增法\n",
    "        mask = 1 << n.bit_length() - 1\n",
    "        powers = []\n",
    "        while mask > 0 and n > 0:\n",
    "            if n >= mask:\n",
    "                powers.append(mask)\n",
    "                n -= mask\n",
    "            mask >>= 1\n",
    "        powers.reverse()\n",
    "        # 前缀积\n",
    "        powers = [*accumulate(powers, mul, initial = 1)]\n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            ans.append(powers[right + 1] // powers[left] % MOD)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        M = 10**9+7\n",
    "        powers = []\n",
    "        while(n > 0):\n",
    "            k = int(math.log(n,2))\n",
    "            powers.append(2**k)\n",
    "            n -= 2**k\n",
    "        powers = powers[::-1]\n",
    "        premul = [1]\n",
    "        for num in powers:\n",
    "            premul.append(premul[-1]*num)\n",
    "        result = []\n",
    "        for l, r in queries:\n",
    "            result.append(premul[r+1] // premul[l] % M)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        # 最低位法\n",
    "        powers = []\n",
    "        while n:\n",
    "            powers.append(lb := n & -n)\n",
    "            n ^= lb\n",
    "\n",
    "        # 前缀积\n",
    "        powers = [*accumulate(powers, mul, initial = 1)]\n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            ans.append(powers[right + 1] // powers[left] % MOD)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        ans = 0 \n",
    "        res = []\n",
    "        for t in range(32):\n",
    "            if 1<<t & n:\n",
    "                res.append(t)\n",
    "        end = []\n",
    "        for i,j in queries:\n",
    "            q = 0\n",
    "            for t in range(i,j+1):\n",
    "                q += res[t]\n",
    "            end.append(pow(2,q,MOD))\n",
    "        return end\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        powers = []\n",
    "        while(n > 0):\n",
    "            k = int(math.log(n,2))\n",
    "            powers.append(2**k)\n",
    "            n -= 2**k\n",
    "        powers = powers[::-1]\n",
    "        premul = [1]\n",
    "        for num in powers:\n",
    "            premul.append(premul[-1]*num)\n",
    "        result = []\n",
    "        for l, r in queries:\n",
    "            result.append(premul[r+1] // premul[l] % (10**9+7))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def power(n):\n",
    "                count = 1/2\n",
    "                res=[]\n",
    "                i=0\n",
    "                while n!=0:\n",
    "                    i=n%2\n",
    "                    n=n//2\n",
    "                    count = int(count*2)\n",
    "                    if i==1:\n",
    "                        res.append(count)\n",
    "                return res\n",
    "        res=[]\n",
    "        power_list= power(n)\n",
    "        for list_power  in queries:\n",
    "            cont=1\n",
    "            left_num= list_power[0]\n",
    "            right_num= list_power[1]\n",
    "            for i in range(left_num,right_num+1):\n",
    "                cont*=power_list[i]\n",
    "            res.append(cont%(10**9+7))\n",
    "        return res        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        powers = list()\n",
    "        p = 1\n",
    "        mod = 10 ** 9 + 7\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                powers.append(p)\n",
    "            n >>= 1\n",
    "            p <<= 1\n",
    "        # print(powers)\n",
    "        ans = list()\n",
    "        for x, y in queries:\n",
    "            tmp = 1\n",
    "            for i in range(x, y + 1):\n",
    "                tmp = tmp * powers[i] % mod\n",
    "            ans.append(tmp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums = []\n",
    "        while n:\n",
    "            nums.append(n % 2)\n",
    "            n //= 2\n",
    "        print(nums)\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i] *= 2**i * nums[i]\n",
    "        print(nums)\n",
    "        nums.sort()\n",
    "        while nums[0] == 0:\n",
    "            nums.pop(0)\n",
    "        res = []\n",
    "        for left,right in queries:\n",
    "            temp = 1\n",
    "            for i in range(left,right+ 1):\n",
    "                temp *= nums[i]\n",
    "            res.append(temp % mod)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        return [reduce(lambda x, y: x * y % MOD, a[l: r + 1]) for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        powers = []\n",
    "        cur = 2**30\n",
    "        while n:\n",
    "            if n>=cur:\n",
    "                powers.append(cur)\n",
    "                n -= cur\n",
    "            else:\n",
    "                cur //= 2\n",
    "\n",
    "        powers.sort()  \n",
    "\n",
    "        answers = []\n",
    "        for left,right in queries:\n",
    "            cur = 1\n",
    "            for i in range(left,right+1):\n",
    "                cur = cur*powers[i]%1000000007\n",
    "            answers.append(cur)\n",
    "        return answers\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        mod=10**9+7\n",
    "        a=[]\n",
    "        while n:\n",
    "            lb=n&-n\n",
    "            a.append(lb)\n",
    "            n^=lb\n",
    "        return [reduce(lambda x,y :x*y%mod,a[l:r+1])for l,r in queries]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10**9 + 7\n",
    "        powers = []\n",
    "        while n:\n",
    "            lobit = n & -n\n",
    "            powers.append(lobit)\n",
    "            n ^= lobit\n",
    "        ans = []\n",
    "        m = len(powers)\n",
    "        res = [[0]*m for _ in range(m)]\n",
    "        for i, p in enumerate(powers):\n",
    "            res[i][i] = p\n",
    "            for j in range(i+1,m):\n",
    "                res[i][j] = res[i][j-1] * powers[j] % MOD\n",
    "        for l, r in queries:\n",
    "            ans.append(res[l][r])\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # for l, r in queries:\n",
    "            # mul = 1\n",
    "            # for p in powers[l:r+1]:\n",
    "            #     mul = mul * p % MOD\n",
    "            # ans.append(mul)\n",
    "        #     mul = reduce(lambda x,y: x*y%MOD, powers[l:r+1])\n",
    "        #     ans.append(mul)\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        powers = []\n",
    "        while n:\n",
    "            lowbit = n & -n\n",
    "            powers.append(lowbit)\n",
    "            n ^= lowbit\n",
    "\n",
    "        # # 1. 暴力\n",
    "        # ans = []\n",
    "        # for l, r in queries:\n",
    "        #     mul = 1\n",
    "        #     for p in powers[l:r+1]:\n",
    "        #         mul = mul * p % MOD\n",
    "        #     ans.append(mul)\n",
    "\n",
    "        # 2. 预处理所有的不同的询问，直接查询\n",
    "        m = len(powers)\n",
    "        res = [[0] * m for _ in range(m)]\n",
    "        for i, p in enumerate(powers):\n",
    "            res[i][i] = p\n",
    "            for j in range(i+1, m):\n",
    "                res[i][j] = res[i][j-1] * powers[j] % MOD\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            ans.append(res[l][r])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        arr, m, k, q = [0], 10 ** 9 + 7, n.bit_length(), [1]\n",
    "        for i in range(k*(k-1)//2):\n",
    "            q.append(q[-1] * 2 % m)\n",
    "        while n:\n",
    "            arr.append(arr[-1] + (n & (-n)).bit_length() - 1)\n",
    "            n &= n-1\n",
    "        return [q[arr[j+1] - arr[i]] for i, j in queries]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        powers = []\n",
    "        while n:\n",
    "            lowbit = n & -n\n",
    "            powers.append(lowbit)\n",
    "            n ^= lowbit\n",
    "\n",
    "        # # 1. 暴力\n",
    "        # ans = []\n",
    "        # for l, r in queries:\n",
    "        #     mul = 1\n",
    "        #     for p in powers[l:r+1]:\n",
    "        #         mul = mul * p % MOD\n",
    "        #     ans.append(mul)\n",
    "\n",
    "        # 2. 预处理所有的不同的询问，直接查询\n",
    "        m = len(powers)\n",
    "        res = [[0] * m for _ in range(m)]\n",
    "        for i, p in enumerate(powers):\n",
    "            res[i][i] = p\n",
    "            for j in range(i+1, m):\n",
    "                res[i][j] = res[i][j-1] * powers[j] % MOD\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            ans.append(res[l][r])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        a = [] # powers 含 最少 数目的 2 的幂\n",
    "        while n:\n",
    "            lb = n & -n # 获取 n「二进制表示的最低位」1\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        \n",
    "        m = len(a)\n",
    "        res = [[0] * m for _ in range(m)] # [l, r] 的答案\n",
    "        \n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            if res[l][r] == 0:\n",
    "                tmp = 1\n",
    "                for i in range(l, r + 1):\n",
    "                    tmp *= a[i] \n",
    "                res[l][r] = tmp % MOD\n",
    "            ans.append(res[l][r])\n",
    "        return ans\n",
    "        \n",
    "        # return [a[r] if r == l else reduce(lambda x, y: x * y % MOD, a[l: r + 1]) for l, r in queries]\n",
    "\n",
    "        # na = len(a)\n",
    "        # res = [[0] * na for _ in range(na)]\n",
    "        # for i, x in enumerate(a):\n",
    "        #     res[i][i] = x\n",
    "        #     for j in range(i + 1, na):\n",
    "        #         res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "        # return [res[l][r] for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        # powers = []\n",
    "        # while n:\n",
    "        #     lowbit = n & -n\n",
    "        #     powers.append(lowbit)\n",
    "        #     n ^= lowbit\n",
    "\n",
    "        # # # 1. 暴力\n",
    "        # # ans = []\n",
    "        # # for l, r in queries:\n",
    "        # #     mul = 1\n",
    "        # #     for p in powers[l:r+1]:\n",
    "        # #         mul = mul * p % MOD\n",
    "        # #     ans.append(mul)\n",
    "\n",
    "        # # # 2. 预处理所有的不同的询问，直接查询\n",
    "        # # m = len(powers)\n",
    "        # # res = [[0] * m for _ in range(m)]\n",
    "        # # for i, p in enumerate(powers):\n",
    "        # #     res[i][i] = p\n",
    "        # #     for j in range(i+1, m):\n",
    "        # #         res[i][j] = res[i][j-1] * powers[j] % MOD\n",
    "        # # ans = []\n",
    "        # # for l, r in queries:\n",
    "        # #     ans.append(res[l][r])\n",
    "\n",
    "\n",
    "        # 3. 幂次的前缀和\n",
    "        pow2 = [1]\n",
    "        for _ in range(500):\n",
    "            pow2.append(pow2[-1] * 2 % MOD) \n",
    "\n",
    "        s = [0]\n",
    "        while n:\n",
    "            lowbit = n & -n\n",
    "            s.append(s[-1] + lowbit.bit_length() - 1)\n",
    "            n ^= lowbit\n",
    "\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            e = s[r+1] - s[l]\n",
    "            # mul = pow(2, e, MOD)\n",
    "            mul = pow2[e]\n",
    "            ans.append(mul)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        na = len(a)\n",
    "        res = [[0] * na for _ in range(na)]\n",
    "        for i, x in enumerate(a):\n",
    "            res[i][i] = x\n",
    "            for j in range(i + 1, na):\n",
    "                res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "        return [res[l][r] for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二进制性质 + 4.因为所有乘数都是2的幂，可以计算幂次的前缀和，通过差分求解区间内2的幂的实际次数，使用快速幂求解（预处理2的不同幂次\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "# 预处理出2的所有幂\n",
    "pow2 = [1] * 500\n",
    "for i in range(1, 500):\n",
    "    pow2[i] = pow2[i-1] * 2 % MOD\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        s = [0]\n",
    "        while n:\n",
    "            lowbit = n & (-n)\n",
    "            s.append(s[-1] + lowbit.bit_length() - 1)\n",
    "            n ^= lowbit\n",
    "\n",
    "        return [pow2[s[r + 1] - s[l]] for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        a = []\n",
    "\n",
    "        while n:\n",
    "\n",
    "            lb = n & -n\n",
    "\n",
    "            a.append(lb)\n",
    "\n",
    "            n ^= lb\n",
    "\n",
    "        na = len(a)\n",
    "\n",
    "        res = [[0] * na for _ in range(na)]\n",
    "\n",
    "        for i, x in enumerate(a):\n",
    "\n",
    "            res[i][i] = x\n",
    "\n",
    "            for j in range(i + 1, na):\n",
    "\n",
    "                res[i][j] = res[i][j - 1] * a[j] % MOD\n",
    "\n",
    "        return [res[l][r] for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二进制性质 + 2.查询数据可能存在大量重复值，可以预处理出所有可能查询情况，然后直接查表返回\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        powers = []\n",
    "        while n:\n",
    "            lowbit = n & (-n)\n",
    "            powers.append(lowbit)\n",
    "            n ^= lowbit\n",
    "\n",
    "        # 预处理\n",
    "        m = len(powers)\n",
    "        res = [[0] * m for _ in range(m)]\n",
    "        for i, x in enumerate(powers):\n",
    "            res[i][i] = x\n",
    "            for j in range(i + 1, m):\n",
    "                res[i][j] = res[i][j-1] * powers[j] % MOD\n",
    "\n",
    "        return [res[l][r] for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        na = len(a)\n",
    "        res = [[0] * na for _ in range(na)]\n",
    "        for i,x in enumerate(a):\n",
    "            res[i][i] = x\n",
    "            for j in range(i+1, na):\n",
    "                res[i][j] = res[i][j-1] * a[j] % MOD\n",
    "        return [res[i][j] for i,j in queries]\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        # MOD = 10 ** 9 + 7\n",
    "        # power = []\n",
    "        # ans = []\n",
    "        # while n:\n",
    "        #     lb = n & -n\n",
    "        #     power.append(lb)\n",
    "        #     n ^= lb\n",
    "        \n",
    "        # for l,r in queries:\n",
    "        #     tmp = power[l:r+1]\n",
    "        #     pro = 1\n",
    "        #     for num in tmp:\n",
    "        #         pro = pro * num  % MOD\n",
    "        #     ans.append(pro)\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pow2 = [1]\n",
    "mod = 10**9+7\n",
    "for i in range(500):\n",
    "    pow2.append(pow2[-1]*2  % mod)\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        # s 幂次前缀和 补零\n",
    "        s = [0]\n",
    "        while n:\n",
    "            lowbit = (-n & n)\n",
    "            s.append(s[-1]+lowbit.bit_length()-1) #有序\n",
    "            n -= lowbit\n",
    "\n",
    "        #幂次前缀和 \n",
    "\n",
    "        ans = [] \n",
    "        for left,right in queries:\n",
    "            e = s[right+1]-s[left]\n",
    "            mul = pow2[e]\n",
    "            ans.append(mul)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 二进制性质 + 4.因为所有乘数都是2的幂，可以计算幂次的前缀和，通过前缀和的差得到区间内的幂次，并预处理出2的不同幂次，对于每个查询直接查表返回\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "# 预处理出2的所有幂\n",
    "pow2 = [2] * 500\n",
    "pow2 = [1] + list(itertools.accumulate(pow2, lambda x, y: x * y % MOD))\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        s = [0]\n",
    "        while n:\n",
    "            lowbit = n & (-n)\n",
    "            s.append(s[-1] + lowbit.bit_length() - 1)\n",
    "            n ^= lowbit\n",
    "\n",
    "        return [pow2[s[r + 1] - s[l]] for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        mod = 10**9+7\n",
    "        power = []\n",
    "        while n:\n",
    "            lowbit = (-n & n)\n",
    "            power.append(lowbit)\n",
    "            n -= lowbit\n",
    "\n",
    "        #预处理\n",
    "        m = len(power)\n",
    "        results = [[0]*m for _ in range(m)]\n",
    "        for i, p in enumerate(power):\n",
    "            results[i][i] = power[i]\n",
    "            for j in range(i+1,m):\n",
    "                results[i][j] = results[i][j-1]* power[j] %mod\n",
    "        ans = [] \n",
    "        for left,right in queries:\n",
    "            product = results[left][right]\n",
    "            ans.append(product)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, q: List[List[int]]) -> List[int]:\n",
    "        mod=10**9+7\n",
    "        n=f\"{n:b}\"\n",
    "        n=n[::-1]\n",
    "        m=len(n)\n",
    "        res=[]\n",
    "        for i in range(m):\n",
    "            if n[i]=='1':\n",
    "                res.append(1<<i)\n",
    "        m=len(res)\n",
    "        p=[1]*m\n",
    "        p[0]=res[0]\n",
    "        for i in range(1,m):\n",
    "            p[i]=(res[i]*p[i-1])%mod\n",
    "        ans=[]\n",
    "        for i,j in q:\n",
    "            if i==0:\n",
    "                ans.append(p[j])\n",
    "            else:\n",
    "                ans.append((p[j]*pow(p[i-1],mod-2,mod))%mod)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def productQueries(self, n: int, queries: list[list[int]]) -> list[int]:\r\n",
    "        #将n转换为二进制\r\n",
    "        n_bin = bin(n)[2:][::-1]\r\n",
    "        pre = [1]\r\n",
    "        n = len(n_bin)\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        for i in range(n):\r\n",
    "            if n_bin[i] == '1':\r\n",
    "                pre.append(pre[-1] * (int(n_bin[i]) * (2 ** i)))\r\n",
    "        ans = [0] * len(queries)\r\n",
    "        n = len(pre)\r\n",
    "        for i in range(len(queries)):\r\n",
    "            l,r = queries[i]\r\n",
    "            if l >= 0 and r + 1 < n:\r\n",
    "                ans[i] = pre[r+1] // pre[l] % MOD\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        arr=[]\n",
    "        for i in range(30):\n",
    "            if n&(1<<i):\n",
    "                arr.append(2**i)\n",
    "        prefix=[1]\n",
    "        for num in arr:\n",
    "            prefix.append(prefix[-1]*num)\n",
    "        ans=[0]*len(queries)\n",
    "        for i,(l,r) in enumerate(queries):\n",
    "            ans[i]=(prefix[r+1]//prefix[l])%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        mod = 10**9+7\n",
    "        power = []\n",
    "        while n:\n",
    "            lowbit = (-n & n)\n",
    "            power.append(lowbit)\n",
    "            n -= lowbit\n",
    "        print(power)\n",
    "        ans = []\n",
    "        for left,right in queries:\n",
    "            product = 1\n",
    "            for p in power[left:right+1]:\n",
    "                product = product*p %mod \n",
    "            ans.append(product)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        s = bin(n)[2:]\n",
    "        powers = []\n",
    "        for i in range(len(s) - 1, -1, -1):\n",
    "            if s[i] == \"1\":\n",
    "                powers.append(len(s) - 1 - i)\n",
    "        prefix = list(accumulate(powers))\n",
    "        MOD = 10**9 + 7\n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            s = prefix[right] - (prefix[left - 1] if left > 0 else 0)\n",
    "            ans.append(2**s % MOD)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def pw(n: int) -> list:\n",
    "    res = []\n",
    "    i = 0\n",
    "    while n:\n",
    "        if n & 1:\n",
    "            res.append(2 ** i)\n",
    "        n >>= 1\n",
    "        i +=1\n",
    "    return res\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        pow2 = pw(n)\n",
    "        ans = [0] * len(queries)\n",
    "        for j, (x, y) in enumerate(queries):\n",
    "            t = 1\n",
    "            for i in range(x, y + 1):\n",
    "                t = (t * pow2[i]) % MOD\n",
    "            ans[j] = t\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        base = 1\n",
    "        ti = 0\n",
    "        while base < n:\n",
    "            base *= 2\n",
    "            ti += 1\n",
    "        lst = []\n",
    "        while n:\n",
    "            while n < base:\n",
    "                base //= 2\n",
    "                ti -= 1\n",
    "            lst.insert(0,ti)\n",
    "            n -= base\n",
    "        # print(lst)\n",
    "        MOD = 10**9+7\n",
    "        res = []\n",
    "\n",
    "        pre_sum = [0]\n",
    "        for i in lst:\n",
    "            pre_sum.append(pre_sum[-1]+i)\n",
    "\n",
    "        for q in queries:\n",
    "            cur_sum = pre_sum[q[1]+1]-pre_sum[q[0]]\n",
    "            cur_res = (2**cur_sum)%MOD\n",
    "            res.append(cur_res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD=10**9+7\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        arr=[]\n",
    "        for i in range(30):\n",
    "            if n&(1<<i):\n",
    "                arr.append(2**i)\n",
    "        prefix=[1]\n",
    "        for num in arr:\n",
    "            prefix.append(prefix[-1]*num)\n",
    "        ans=[0]*len(queries)\n",
    "        for i,(l,r) in enumerate(queries):\n",
    "            ans[i]=(prefix[r+1]//prefix[l])%MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        return [reduce(lambda x, y: x * y % MOD, a[l: r + 1]) for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10**9 + 7\n",
    "        s = [0]\n",
    "        while n:\n",
    "            lowbit = n & -n\n",
    "            s.append(s[-1] + lowbit.bit_length() - 1)\n",
    "            n ^= lowbit\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            e = s[r+1] - s[l]\n",
    "            mul = pow(2,e,MOD)\n",
    "            ans.append(mul)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        # powers = []\n",
    "        # while n:\n",
    "        #     lobit = n & -n\n",
    "        #     powers.append(lobit)\n",
    "        #     n ^= lobit\n",
    "        # ans = []\n",
    "        # m = len(powers)\n",
    "        # res = [[0]*m for _ in range(m)]\n",
    "        # for i, p in enumerate(powers):\n",
    "        #     res[i][i] = p\n",
    "        #     for j in range(i+1,m):\n",
    "        #         res[i][j] = res[i][j-1] * powers[j] % MOD\n",
    "        # for l, r in queries:\n",
    "        #     ans.append(res[l][r])\n",
    "        # return ans\n",
    "\n",
    "        # for l, r in queries:\n",
    "            # mul = 1\n",
    "            # for p in powers[l:r+1]:\n",
    "            #     mul = mul * p % MOD\n",
    "            # ans.append(mul)\n",
    "        #     mul = reduce(lambda x,y: x*y%MOD, powers[l:r+1])\n",
    "        #     ans.append(mul)\n",
    "        # return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        base = 1\n",
    "        ti = 0\n",
    "        while base < n:\n",
    "            base = base << 1\n",
    "            ti += 1\n",
    "        lst = []\n",
    "        while n:\n",
    "            while n < base:\n",
    "                base = base >> 1 \n",
    "                ti -= 1\n",
    "            lst.insert(0,ti)\n",
    "            n -= base\n",
    "        # print(lst)\n",
    "        MOD = 10**9+7\n",
    "        res = []\n",
    "\n",
    "        pre_sum = [0]\n",
    "        for i in lst:\n",
    "            pre_sum.append(pre_sum[-1]+i)\n",
    "\n",
    "        for q in queries:\n",
    "            cur_sum = pre_sum[q[1]+1]-pre_sum[q[0]]\n",
    "            cur_res = (1<<cur_sum)%MOD\n",
    "            res.append(cur_res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        return [reduce(lambda x, y: x * y % MOD, a[l: r + 1]) for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        lst = []\n",
    "        while n:\n",
    "            lst.append(n&(-n))\n",
    "            n &= n-1\n",
    "        pre = list(accumulate(lst, mul, initial=1))\n",
    "        mod = 10**9+7\n",
    "        return [(pre[y+1]//pre[x]) % mod for x, y in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        c = [0]\n",
    "        for i in range(32):\n",
    "            if n >> i & 1:\n",
    "                c.append(i+c[-1])\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            ans.append(pow(2, c[r+1]-c[l], MOD))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        def find_powers(n):\n",
    "            curr = 1\n",
    "            res = []\n",
    "            while curr * 2 <= n:\n",
    "                curr = curr * 2\n",
    "            while n > 0:\n",
    "                while curr > n:\n",
    "                    curr = curr // 2\n",
    "                n -= curr\n",
    "                res.append(curr)\n",
    "            return res[::-1]\n",
    "\n",
    "        powers = find_powers(n)\n",
    "        pre_product = [1 for _ in range(len(powers) + 1)]\n",
    "        res = []\n",
    "        for i in range(1, len(pre_product)):\n",
    "            pre_product[i] = pre_product[i-1] * powers[i-1]\n",
    "        for start, end in queries:\n",
    "            res.append(pre_product[end+1] // pre_product[start] % (10 ** 9 + 7))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        power = []\n",
    "        while n:\n",
    "            lowbit = n & -n\n",
    "            power.append(lowbit)\n",
    "            n ^= lowbit\n",
    "        npower = len(power)\n",
    "        prepro = list(accumulate(power, lambda x,y:x*y, initial = 1))\n",
    "        return [prepro[r + 1] // prepro[l] % MOD for l, r in queries]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        base = 1\n",
    "        ti = 0\n",
    "        while base < n:\n",
    "            base *= 2\n",
    "            ti += 1\n",
    "        lst = []\n",
    "        while n:\n",
    "            while n < base:\n",
    "                base //= 2\n",
    "                ti -= 1\n",
    "            lst.insert(0,ti)\n",
    "            n -= base\n",
    "        # print(lst)\n",
    "        MOD = 10**9+7\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            cur_sum = 0\n",
    "            for i in range(q[0],q[1]+1):\n",
    "                cur_sum += lst[i]\n",
    "            cur_res = (2**cur_sum)%MOD\n",
    "            res.append(cur_res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二进制性质 + 5.前缀积 + 求逆元，类似通过前缀和的差求区间和的思路，差别在于减法变成了除法，且由于MOD操作的存在，要使用乘以逆元的方式\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # 求s的前缀积及其逆元\n",
    "        s = [1]\n",
    "        while n:\n",
    "            lowbit = n & (-n)\n",
    "            s.append(s[-1] * lowbit)\n",
    "            n ^= lowbit\n",
    "        invS = [0] * len(s)\n",
    "        for i, x in enumerate(s):\n",
    "            invS[i] = pow(x, MOD - 2, MOD)\n",
    "\n",
    "        return [s[r + 1] * invS[l] % MOD for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "#         MOD = 10 ** 9 + 7\n",
    "#         power = []\n",
    "#         ans = []\n",
    "#         while n:\n",
    "#             lb = n & -n\n",
    "#             power.append(lb)\n",
    "#             n ^= lb\n",
    "        \n",
    "#         for l,r in queries:\n",
    "#             tmp = power[l:r+1]\n",
    "#             pro = 1\n",
    "#             for num in tmp:\n",
    "#                 pro = pro * num  % MOD\n",
    "#             ans.append(pro)\n",
    "#         return ans\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        a = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            a.append(lb)\n",
    "            n ^= lb\n",
    "        return [reduce(lambda x, y: x * y % MOD, a[l: r + 1]) for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        q=[]\n",
    "        while n:\n",
    "           x=1 \n",
    "           while x*2<=n:\n",
    "             x*=2\n",
    "           n-=x\n",
    "           q.append(x)\n",
    "        q=q[::-1]\n",
    "        f=[1]\n",
    "        for x in q:\n",
    "         f.append(f[-1]*x)\n",
    "        ans=[]\n",
    "        for x in queries:\n",
    "          ans.append((f[x[1]+1]//f[x[0]])%(10**9+7))  \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二进制性质 + 3.因为所有乘数都是2的幂，可以计算幂次的前缀和，通过差分求解区间内2的幂的实际次数，使用快速幂求解（裸算）\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        s = [0]\n",
    "        while n:\n",
    "            lowbit = n & (-n)\n",
    "            s.append(s[-1] + lowbit.bit_length() - 1)\n",
    "            n ^= lowbit\n",
    "\n",
    "        return [pow(2, s[r + 1] - s[l], MOD) for l, r in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        i = 0\n",
    "        lis = []\n",
    "        mod=10**9+7\n",
    "        while 2**i<=n:\n",
    "            i+=1\n",
    "        for j in range(i,-1,-1):\n",
    "            s = 2**j\n",
    "            if n>=s:\n",
    "                lis.insert(0,s)\n",
    "                n-=s\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            c = 1\n",
    "            for i in range(q[0],q[1]+1):\n",
    "                c*=lis[i]\n",
    "            d = c%mod\n",
    "            ans.append(d)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        mod = 10**9+7\n",
    "        # s 幂次前缀和 补零\n",
    "        s = [0]\n",
    "        while n:\n",
    "            lowbit = (-n & n)\n",
    "            s.append(s[-1]+lowbit.bit_length()-1) #有序\n",
    "            n -= lowbit\n",
    "\n",
    "        #幂次前缀和\n",
    "        ans = [] \n",
    "        for left,right in queries:\n",
    "            e = s[right+1]-s[left]\n",
    "            mul = pow(2,e,mod) #python 自动取模快速幂\n",
    "            ans.append(mul)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10**9 + 7\n",
    "        \n",
    "        # 步骤1: 找到n可以表示为2的幂的和\n",
    "        powers = []\n",
    "        while n > 0:\n",
    "            # 找到最大的2的幂，它不超过n\n",
    "            power = 2**int(math.log2(n))\n",
    "            powers.append(power)\n",
    "            n -= power\n",
    "        \n",
    "        # 步骤2: 使用一个列表powers来存储这些2的幂\n",
    "        # 注意：我们从最大的2的幂开始添加，所以需要反转列表以满足非递减的要求\n",
    "        powers.reverse()\n",
    "        \n",
    "        # 步骤3: 对于每个查询，找到给定索引范围内2的幂的乘积\n",
    "        answers = []\n",
    "        for left, right in queries:\n",
    "            prod = 1\n",
    "            for i in range(left, right + 1):\n",
    "                prod = (prod * powers[i]) % MOD\n",
    "            answers.append(prod)\n",
    "        \n",
    "        return answers\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        arr = []\n",
    "        for i in range(32):\n",
    "            if (1 << i) & n:\n",
    "                arr.append(i)\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            t = 1\n",
    "            for i in range(l, r+1):\n",
    "                t *= int(pow(2, arr[i]))\n",
    "                t %= (10 ** 9 + 7)\n",
    "            ans.append(t % (10 ** 9 + 7))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        # powers = []\n",
    "        # while n:\n",
    "        #     lowbit = n & -n\n",
    "        #     powers.append(lowbit)\n",
    "        #     n ^= lowbit\n",
    "\n",
    "        # # # 1. 暴力\n",
    "        # # ans = []\n",
    "        # # for l, r in queries:\n",
    "        # #     mul = 1\n",
    "        # #     for p in powers[l:r+1]:\n",
    "        # #         mul = mul * p % MOD\n",
    "        # #     ans.append(mul)\n",
    "\n",
    "        # # # 2. 预处理所有的不同的询问，直接查询\n",
    "        # # m = len(powers)\n",
    "        # # res = [[0] * m for _ in range(m)]\n",
    "        # # for i, p in enumerate(powers):\n",
    "        # #     res[i][i] = p\n",
    "        # #     for j in range(i+1, m):\n",
    "        # #         res[i][j] = res[i][j-1] * powers[j] % MOD\n",
    "        # # ans = []\n",
    "        # # for l, r in queries:\n",
    "        # #     ans.append(res[l][r])\n",
    "\n",
    "\n",
    "        # 3. 幂次的前缀和\n",
    "        s = [0]\n",
    "        while n:\n",
    "            lowbit = n & -n\n",
    "            s.append(s[-1] + lowbit.bit_length() - 1)\n",
    "            n ^= lowbit\n",
    "\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            e = s[r+1] - s[l]\n",
    "            mul = pow(2, e, MOD)\n",
    "            ans.append(mul)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10**9+7\n",
    "        p, ans = [], []\n",
    "        for i,b in enumerate(bin(n)[2:]):\n",
    "            if b == '1':\n",
    "                p.append(n.bit_length()-i-1)\n",
    "        p = p[::-1]\n",
    "        ps = list(accumulate(p))\n",
    "        ps.append(0)\n",
    "        for l,r in queries:\n",
    "            ans.append((1 << (ps[r]-ps[l-1]))%MOD)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二进制性质 + 1.暴力枚举（python中可以使用reduce函数实现连乘）\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        powers = []\n",
    "        while n:\n",
    "            lowbit = n & (-n)\n",
    "            powers.append(lowbit)\n",
    "            n ^= lowbit\n",
    "\n",
    "        return [reduce(lambda x, y: x * y,  powers[l: r + 1]) % MOD for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        res = [0]*len(queries)\n",
    "        powers = []\n",
    "        while n:\n",
    "            bit = n & -n\n",
    "            powers.append(bit)\n",
    "            n -= bit\n",
    "        accu = list(accumulate(powers, operator.mul, initial=1))\n",
    "        M = 10**9+7\n",
    "        for i, (l, r) in enumerate(queries):\n",
    "            res[i] = accu[r+1] // accu[l] % M\n",
    "        return res\n",
    "        # for powerOff, resOff in sorted(chain.from_iterable([[l, -i], [r, i]] for i, (l, r) in enumerate(queries))):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        powers = []\n",
    "        while n:\n",
    "            lowbit = n & (-n)\n",
    "            powers.append(lowbit)\n",
    "            n ^= lowbit\n",
    "\n",
    "        return [reduce(lambda x, y: x * y,  powers[l: r + 1]) % MOD for l, r in queries]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        power = []\n",
    "        ans = []\n",
    "        while n:\n",
    "            lb = n & -n\n",
    "            power.append(lb)\n",
    "            n ^= lb\n",
    "        \n",
    "        for l,r in queries:\n",
    "            tmp = power[l:r+1]\n",
    "            pro = 1\n",
    "            for num in tmp:\n",
    "                pro = pro * num  % MOD\n",
    "            ans.append(pro)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        cnt = [0]\n",
    "        k = 0\n",
    "        M = 10 ** 9 + 7\n",
    "        one = 0\n",
    "        while n:\n",
    "            if n & 1:\n",
    "                cnt.append(one)\n",
    "            one += 1\n",
    "            n >>= 1\n",
    "        n = len(cnt)\n",
    "        print(cnt)\n",
    "        for i in range(1, n):\n",
    "            cnt[i] += cnt[i - 1]\n",
    "        ret = []\n",
    "        for s, e in queries:\n",
    "            k = cnt[e + 1] - cnt[s]\n",
    "            x = 1\n",
    "            while k:\n",
    "                k -= 1\n",
    "                x = (x * 2) % M\n",
    "            ret.append(x)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10**9 + 7\n",
    "        powers = []\n",
    "        while n:\n",
    "            lobit = n & -n\n",
    "            powers.append(lobit)\n",
    "            n ^= lobit\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            mul = 1\n",
    "            for p in powers[l:r+1]:\n",
    "                mul = mul * p % MOD\n",
    "            ans.append(mul)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: list[list[int]]) -> list[int]:\n",
    "        def fun(left,right):\n",
    "            t= 1\n",
    "            for i in range(left,right+1):\n",
    "                t*=powers[i]\n",
    "                t=t%(10**9+7)\n",
    "            return t\n",
    "        s = bin(n)[2:]\n",
    "        s=s[-1::-1]\n",
    "        powers=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i]=='1':\n",
    "                powers.append(2**i)\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            ans.append(fun(q[0],q[1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        MOD = 10**9 + 7\n",
    "        powers = []\n",
    "        while n:\n",
    "            lobit = n & -n\n",
    "            powers.append(lobit)\n",
    "            n ^= lobit\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            # mul = 1\n",
    "            # for p in powers[l:r+1]:\n",
    "            #     mul = mul * p % MOD\n",
    "            # ans.append(mul)\n",
    "            mul = reduce(lambda x,y: x*y%MOD, powers[l:r+1])\n",
    "            ans.append(mul)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        powers = []\n",
    "        while n:\n",
    "            lowbit = n & -n\n",
    "            powers.append(lowbit)\n",
    "            n ^= lowbit\n",
    "\n",
    "        # 1. 暴力\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            mul = 1\n",
    "            for p in powers[l:r+1]:\n",
    "                mul = mul * p % MOD\n",
    "            ans.append(mul)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# 二进制性质 + 1.暴力枚举（python中可以使用reduce函数实现连乘）\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        powers = []\n",
    "        while n:\n",
    "            lowbit = n & (-n)\n",
    "            powers.append(lowbit)\n",
    "            n ^= lowbit\n",
    "\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            mul = reduce(lambda x, y: x * y,  powers[l: r + 1]) % MOD\n",
    "            ans.append(mul)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        powers = []\n",
    "        power = 0\n",
    "        while n > 0:\n",
    "            if n % 2 == 1:\n",
    "                powers.append(2 ** power)\n",
    "            n //= 2\n",
    "            power += 1\n",
    "\n",
    "        answers = []\n",
    "        mod = 10**9 + 7\n",
    "        for left, right in queries:\n",
    "            product = 1\n",
    "            for i in range(left, right + 1):\n",
    "                product = (product * powers[i]) % mod\n",
    "            answers.append(product)\n",
    "\n",
    "        return answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:\n",
    "        i = 1\n",
    "        idx = 0\n",
    "        l = []\n",
    "        while i <= n:\n",
    "            if i & n:\n",
    "                l.append(idx)\n",
    "            i *= 2\n",
    "            idx += 1\n",
    "        dp = [[0]*len(l) for i in range(len(l))]\n",
    "        for i in range(len(l)):\n",
    "            for j in range(i,len(l)):\n",
    "                if i == j:\n",
    "                    dp[i][j] = l[i]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1] + l[j]\n",
    "        ans = []\n",
    "        for i in queries:\n",
    "            left = i[0]\n",
    "            right = i[1]\n",
    "            v = pow(2,dp[left][right]) % (10**9+7)\n",
    "            ans.append(v)\n",
    "\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
